#include <stdio.h>
#include<cstdlib>

struct AvlNode;
typedef struct AvlNode *Postion;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty ( AvlTree T );
Postion Find( int X , AvlTree T );
Postion FindMin( AvlTree T );
Postion FindMax( AvlTree T );
AvlTree Insert( int X, AvlTree T );
AvlTree Delete( int X, AvlTree T );
int Retrieve( Postion P );
static Postion  SingleRotateWithLeft( Postion P );
static Postion  SingleRotateWithRight( Postion P );
int Max( int x, int y);

struct AvlNode
{
    int Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

static int
Height( Postion P )
{
    if( P == NULL )
        return -1;
    else
        return P->Height;
}

int Max( int x, int y)
{
    if(x >= y) return x;
    else return y;
}

AvlTree
Insert( int X, AvlTree T)
{
    if( T == NULL )
    {
        T = malloc(sizeof(struct AvlNode));
        if (T == NULL)
            printf("Out of space!!!");
        else {
            T->Element = X;
            T->Height = 0;
        }
    }
    else if( X < T ->Element )
    {
        T->Left = Insert( X , T->Left);
        if( Height( T-> Left ) - Height( T->Right) == 2)
            if( X < T->Left->Element )
                T = SingleRotateWithLeft( T );
            else
                T = SingleRotateWithLeft( T );
    }
    else if( X > T->Element )
    {
        T->Right = Insert( X , T->Right);
        if(Height( T->Right) - Height(T->Left) == 2)
            if( X < T->Left->Element )
                T = SingleRotateWithRight( T );
            else
                T = SingleRotateWithRight( T );
    }

    T->Height = Max( Height( T->Left),Height( T->Right ) ) + 1;
    return T;
}